/*
 * z-функция
 * vim:foldmethod=marker:
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INPUT_MAXLEN	(128000UL + 1UL) //including '\n'
#define MIN(a, b)	((a) < (b) ? (a) : (b))

unsigned long _string_len = 0;

int *
z_func(const char *s, int *z)
{
	int i, l, r;

	memset(z, 0, _string_len * sizeof *z);

	for (i = 1, l = 0, r = 0; i < _string_len; ++i) {
		if (i <= r)
			z[i] = MIN(r - i + 1, z[i - l]);
		while (i + z[i] < _string_len && s[z[i]] == s[i + z[i]])
			++z[i];
		if (i + z[i] - 1 > r)
			l = i, r = i + z[i] - 1;
	}

	return z;
}

int
main(void)
{
	char	*string;
	int	*z;
	int	i = 0;

	string	= (char *) malloc((INPUT_MAXLEN + 1UL) * sizeof *string);
	z	= (int *)  malloc(INPUT_MAXLEN * sizeof *z);

	while (fgets(string, INPUT_MAXLEN, stdin)) {
		_string_len = strlen(string);

		if (string[_string_len - 1] == '\n')
			string[--_string_len] = '\0';

		z_func(string, z);

		i = 1;
		while (i < _string_len)
			(void) printf("%d ", z[i++]);
		putc('\n', stdout);
	}

	free(z);
	free(string);

	return 0;
}
